//
//  Problem454.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/12.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 454. 四数相加 II
 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

 例如:
输入:
     A = [ 1, 2]
     B = [-2,-1]
     C = [-1, 2]
     D = [ 0, 2]
 输出:
    2

 解释:
     两个元组如下:
     1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
     2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
 */
@objcMembers class Problem454: NSObject {
    func solution() {
        print(fourSumCount([ 1, 2], [-2,-1], [-1, 2], [ 0, 2]))
    }
    
    /*
     哈希表：
     1：将nums1和nums2合并成一个哈希表，统计n1+n2的个数
     2: 将nums3和nums4合并成一个进行计算，计算-n3-n4在哈希表中的个数
     */
    func fourSumCount(_ nums1: [Int], _ nums2: [Int], _ nums3: [Int], _ nums4: [Int]) -> Int {
        var map:[Int : Int] = [:]
        for n1 in nums1 {
            for n2 in nums2 {
                map[n1+n2, default: 0] += 1
            }
        }
        var result = 0
        for n3 in nums3 {
            for n4 in nums4 {
                if map[-n3-n4] != nil {
                    result += map[-n3-n4]!
                }
            }
        }
        return result
    }
}
